<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Cayley-Formel</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Cayley-Formel"> <link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Cayley-Formel rootpage-Cayley-Formel skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Cayley-Formel</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">
<p>Die <b>Cayley-Formel</b> (benannt nach <a href="Arthur_Cayley" title="Arthur Cayley">Arthur Cayley</a>), manchmal auch <b>Satz von Cayley</b> genannt, ist ein Satz aus der <a href="Abz%C3%A4hlende_Kombinatorik" title="Abzählende Kombinatorik">abzählenden Kombinatorik</a>.
Er besagt, dass es <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{n-2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n^{n-2}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65a6e7866523a163c773c59df1fc7793ef534c56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.714ex; height:2.676ex;" alt="{\displaystyle n^{n-2}}" loading="lazy"></span> verschiedene bezeichnete <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Bäume</a> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten gibt.
</p>
<div class="mw-heading mw-heading2"><h2 id="Formulierungen">Formulierungen</h2></div>
<ul><li>Es gibt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{n-2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n^{n-2}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65a6e7866523a163c773c59df1fc7793ef534c56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.714ex; height:2.676ex;" alt="{\displaystyle n^{n-2}}" loading="lazy"></span> verschiedene bezeichnete <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Bäume</a> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten.</li>
<li>Der bezeichnete <a href="Vollst%C3%A4ndiger_Graph" title="Vollständiger Graph">vollständige Graph</a> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten hat <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{n-2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>n</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n^{n-2}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65a6e7866523a163c773c59df1fc7793ef534c56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.714ex; height:2.676ex;" alt="{\displaystyle n^{n-2}}" loading="lazy"></span> verschiedene <a href="Spannbaum" title="Spannbaum">aufspannende Bäume</a>.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Beweise">Beweise</h2></div>
<p>Für die Cayley-Formel gibt es unzählige Beweise, einige davon werden von vielen Mathematikern als besonders schön angesehen.
Das spiegelt sich unter anderem in der Tatsache, dass der Cayley-Formel ein Kapitel in <i><a href="Das_Buch_der_Beweise" title="Das Buch der Beweise">Das Buch der Beweise</a></i> gewidmet ist.
Dort werden vier verschiedene Beweise präsentiert:
</p>
<ol><li>mittels einer <a href="Bijektion" class="mw-redirect" title="Bijektion">Bijektion</a> von der Menge aller Bäume in eine einfacher zu zählende Menge (siehe <a href="Pr%C3%BCfer-Code" title="Prüfer-Code">Prüfer-Code</a>),</li>
<li>unter Verwendung des <a href="Satz_von_Kirchhoff" title="Satz von Kirchhoff">Satzes von Kirchhoff</a>,</li>
<li>mittels <a href="Rekursion" title="Rekursion">Rekursion</a>,</li>
<li>durch <a href="Doppeltes_Abz%C3%A4hlen" title="Doppeltes Abzählen">doppeltes Abzählen</a>.</li></ol>
<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>
<p>Die Formel wurde zuerst von <a href="Karl_Wilhelm_Borchardt" title="Karl Wilhelm Borchardt">Carl Wilhelm Borchardt</a> (1860) publiziert.
1889 erweiterte Cayley die Formel und formulierte sie in der Graphenterminologie, weshalb sie seitdem mit seinem Namen verbunden wird.
</p><p>Auch erwähnenswert ist, dass <a href="James_Joseph_Sylvester" title="James Joseph Sylvester">James Joseph Sylvester</a> schon (1857) ein äquivalentes Resultat publizierte.
</p>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li>Martin Aigner, <a href="G%C3%BCnter_Ziegler" title="Günter Ziegler">Günter M. Ziegler</a>: <cite style="font-style:italic"><a href="Das_Buch_der_Beweise" title="Das Buch der Beweise">Das Buch der Beweise</a></cite>. Springer-Verlag, 2010, Kapitel 30 – <i>Cayleys Formel für die Anzahl der Bäume</i>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>227–233</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abookitem&rfr_id=info:sid/de.wikipedia.org:Cayley-Formel&rft.atitle=Kapitel+30+-+Cayleys+Formel+f%C3%BCr+die+Anzahl+der+B%C3%A4ume&rft.au=Martin+Aigner%2C+G%C3%BCnter+M.+Ziegler&rft.btitle=Das+Buch+der+Beweise&rft.date=2010&rft.genre=bookitem&rft.pages=227-233&rft.pub=Springer-Verlag" style="display:none"> </span></li>
<li>Borchardt, C.W.: <cite style="font-style:italic">Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung</cite>. In: <cite style="font-style:italic">Math. Abh. der Akademie der Wissenschaften zu Berlin</cite>. 1860, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>1–20</span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Cayley-Formel&rft.atitle=%C3%9Cber+eine+Interpolationsformel+f%C3%BCr+eine+Art+Symmetrischer+Functionen+und+%C3%BCber+Deren+Anwendung&rft.au=Borchardt%2C+C.W.&rft.btitle=Math.+Abh.+der+Akademie+der+Wissenschaften+zu+Berlin&rft.date=1860&rft.genre=book&rft.pages=1-20" style="display:none"> </span></li>
<li>A. Cayley: <cite style="font-style:italic">A theorem on trees</cite>. In: <cite style="font-style:italic">Quart. J. Math</cite>. 23. Jahrgang, 1889, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>376–378</span> (<a rel="nofollow" class="external text" href="http://books.google.com/?id=M7c4AAAAIAAJ&pg=PA26">google.com</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Cayley-Formel&rft.atitle=A+theorem+on+trees&rft.au=A.+Cayley&rft.btitle=Quart.+J.+Math&rft.date=1889&rft.genre=book&rft.pages=376-378&rft.volume=23.+Jahrgang" style="display:none"> </span></li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2017-03-25" href="https://de.wikipedia.org/wiki/?title=Cayley-Formel&oldid=163928667">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>